package com.str.tree;

public class TreeOps {

	// Each LinkedTree object is an unordered tree whose
	// elements are arbitrary objects.
	// This tree is represented by a reference to its root TreeNode (root),
	// which
	// is null if the tree is empty. Each tree TreeNode contains links to its
	// first
	// child, to its parent, and to its next sib.

	public static void insertFirst(TreeNode curr, Object val) {
		// Add a new TreeNode containing element elem as a child of TreeNode in
		// this
		// tree. The new TreeNode has no children of its own. Return the
		// TreeNode
		// just added.
		curr.leftChild = new TreeNode(val, null, curr.leftChild);
	}

	public static void insertNext(TreeNode curr, Object val) {
		// Add a new TreeNode containing element elem as a child of TreeNode in
		// this
		// tree. The new TreeNode has no children of its own. Return the
		// TreeNode
		// just added.
		curr.rightSib = new TreeNode(val, null, curr.rightSib);
	}

	public static Object removeFirst(TreeNode curr) {
		// Remove TreeNode from this tree, together with all its descendants.
		if (curr.leftChild == null)
			return null;
		Object temp = curr.leftChild.data;
		curr.leftChild = curr.leftChild.rightSib;
		return temp;
	}

	public static Object removeNext(TreeNode curr) {
		// Remove TreeNode from this tree, together with all its descendants.
		if (curr.rightSib == null)
			return null;
		Object temp = curr.rightSib.data;
		curr.rightSib = curr.rightSib.rightSib;
		return temp;
	}

	public static TreeNode search(TreeNode ref, Object val) {
		if (ref == null)
			return null;
		if (val.equals(ref.data))
			return ref;
		TreeNode child = ref.leftChild;
		while (child != null) {
			ref = search(child, val);
			if (ref != null)
				return ref;
			child = child.rightSib;
		}
		return child;
	}

	public static void print(TreeNode ref) {
		// Convert this (sub-)tree into a string representation.
		if (ref == null)
			System.out.println("Empty tree");
		else {
			TreeNode child = ref.leftChild;
			if (child == null)
				System.out.print("Leaf: ");
			else
				System.out.print("Internal: ");
			System.out.println(ref.data);
			while (child != null) {
				print(child);
				child = child.rightSib;
			}
		}
	}
}